14. 最长公共前缀

#leetcode/longest-common-prefix #leetcode/lexicographical-order #leetcode/sort/merge

14. Longest Common Prefix

Similar Question

leading to the advanced question

Solution Tips

方案

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // 以第一个字符串为基础遍历, 同时遍历其他多个字符串, 感觉容易溢出
    // 字符串有 startWith 方法
    // 不应该字母都全都判断一次, 可以直接提取前两个字符串的最长, 如果第三个不符合再回退?
    // 1和2的最长公共, 再和3找出最长公共, 直到最后
    // 也可以看做二维数组, 每次遍历一列
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        const str = strs[i];
        // 找出 str 和 prefix 的最长公共前缀, 双指针
        prefix = findLCP(prefix, str)
		// prefix 为空串了就可以提前退出
    }

    return prefix;
};

function findLCP(str1, str2) {
    let res = '';
    for (let i = 0; i < str1.length; i++) {
        const char = str1[i];
        if (char === str2[i]) {
            res += char;
        }
        else {
            return res;
        }
    }
    return res;
}

console.log(longestCommonPrefix(["flower","flow","flight"]))
console.log(longestCommonPrefix(["dog","racecar","car"]))

方案二: 垂直比较

  /**
   * @param {string[]} strs
   * @return {string}
   */
  var longestCommonPrefix = function(strs) {
    let prefix = ''
  
    let min = Math.MAX_SAFE_INTEGER
    if(strs.length <= 1) return strs[0] || ""
    // 先找出最短的字符串
    for (let i = 0; i < strs.length; i++) {
      let currentLength = strs[i].length
      if(currentLength < min){
        min = currentLength
      }
    }
    // 左对齐，垂直比较
    for (let j = 0; j < min; j++) {
      let current = strs[0][j]
      for (let i = 0; i < strs.length; i++) {
        if(strs[i][j] !== current){
          return prefix
        }
      }
      prefix += strs[0][j]
    }
    return prefix || ""
  };

方案三: 字典序

  var longestCommonPrefix = function (strs) {
    let prefix = ''
    if (!strs) return ''
  
    strs.sort()
    console.log(strs)
    // 默认按照unicode码排序，排序之后，比较第一个和最后一个即可
    last = strs[strs.length - 1]
    if(!last) return ''
    lastLen = last.length
    length = Math.min(strs[0].length, lastLen)
    for (let i = 0; i < length; i++) {
      if (strs[0][i] === last[i]) {
        prefix += strs[0][i]
      }else{
        return prefix || ''
      }
    }
  
    return prefix || ''
  };
  
  console.log(longestCommonPrefix(['abc','abb']))